Memory latency, i.e., the time required to access data or instructions stored in the memory of a computer, has increasingly become the bottleneck that prevents the full realization of the speed of contemporary single and multiprocessor computer systems. This result is occurring because the speed of integrated processors has outstripped memory subsystem speed. In order to operate most efficiently and effectively, fast processors require the contradictory features of reduced memory latency and larger memory size. Larger memory size implies greater physical size, greater communication distances, and slower access time due to the additional signal buffers needed to drive heavily loaded address, data and control signal lines, all of which increase memory latency. The primary negative effect of memory latency is its effect on processor speed. The longer it takes to obtain data from memory, the slower a processor runs because processors usually remain idle when they are waiting for data. This negative effect has increased as processor speed has outstripped memory subsystem speed. Despite the gains made in high-density, high-speed integrated memories, the progress to date still leaves the memory subsystem as the speed-limiting link in computer system design. This is true regardless of whether the computer system includes a single processor or a plurality of processors.
One way to reduce average memory latency is to add a cache subsystem to a computer system. A cache subsystem consists of a small memory situated adjacent to a processor that is hardware controlled rather than software controlled. Frequently used datum and instructions are replicated in cache memories. Cache subsystems capitalize on the property that once a datum or instruction has been fetched from system memory, it is very likely that it will be reused in the near future. Due to the close association between cache memory and its associated processor and the nature of the control (hardware as opposed to software), cache memory latency is several times less than that of system memory. Because access is much more rapid, overall speed is improved in computer systems that include a cache subsystem. As memory latency increases with memory size, hierarchical caches have been developed to maintain average memory latency at a low level. Some high-performance processors include separate instruction and datum caches that can be simultaneously accessed. (For simplicity of description, datum, instructions and any other forms of information commonly stored in computer memories are collectively hereinafter referred to as data.)
While computer systems that include a cache subsystem have a number of advantages, one disadvantage is the expense of cache memories. This disadvantage is enhanced because a cache memory does not add capacity to system memory. Rather, cache memories are add-ons to system memory, because, as noted above, cache memories replicate data stored in system memory. The replication of data leads to another disadvantage of cache memories, namely, the need to maintain coherency between data stored at two or more locations in the memories of a computer system. More specifically, because data stored at either location can be independently updated, a computer system that includes a cache subsystem requires a way of maintaining coherency between independent sources of the same data. If coherency is not maintained, data at one location will become stale when the same data at another location is updated. The use of stale data can lead to errors.
Several different types of cache management algorithms have been developed to govern what occurs when data stored in a cache are updated. The simplest algorithm is known as a "write-through" cache coherency management protocol. A write-through cache coherency management protocol causes processor writes to be propagated directly to system memory. All caches throughout the computer system are searched, and any copies of written data are either invalidated or updated. While a write-through cache coherency management protocol can be used with multiprocessor computer systems that include a large number of processors, a write-through cache coherency management protocol is better suited for single processor computer systems or multiprocessor computer systems incorporating a limited number, e.g., four, of processors.
A more complex, but higher performance, coherency management algorithm is known as a "write-back" cache coherency management protocol. Like a write-through cache coherency management protocol, a write-back cache coherency management protocol is an algorithm that is normally incorporated in the hardware of a computer system that controls the operation of a cache. In a write-back cache coherency management protocol, initial processor writes are written only to cache memory. Later, as necessary, updated data stored in a cache memory is transferred to system memory. Updated data transfer occurs when an input/output device or another processor requires the updated data. A write-back cache coherency management protocol is better suited for use in multiprocessor computer systems that include a large number of processors (e.g., 24) than a write-through cache coherency management protocol because a write-back cache coherency management protocol has a lower impact on the system interconnect because a write-through cache coherency management protocol greatly reduces write traffic.
One of the first write-back coherency management protocols was suggested by Dr. James R. Goodman in his paper entitled "Using Cache Memory to Reduce Processor Memory Traffic" (10th International Symposium of Computer Architecture, 1983). Dr. Goodman's improvement is based on the observation that if the sole copy of data associated with a specific system memory location is stored in a cache, the cache copy can be repeatedly modified without the need to broadcast write-invalidate messages to all other system caches each time a modification occurs. More specifically, Dr. Goodman's improvement requires the addition of a state bit to each cache copy. The state bit indicates that the copy is either "shared" or "owned." When a system memory location is first read, and data supplied to a cache, the state bit is set to the "shared" state. If the cache copy is later written, i.e., modified, the state bit transitions to the "owned" state. At the same time, a write-invalidate message is broadcast, resulting in the updated cache copy of the data being identified as the only valid copy associated with the related system memory location. As long as the cache location remains in an owned state, it can be rewritten, i.e., updated, without the need to broadcast further write-invalidate messages. A remote request for the data to the memory location associated with the cached copy causes a transition back to the shared state, and the read request to be satisfied by either the cache and, then, updating the related system memory location, or by the cache delaying the memory request until valid data is rewritten to the system memory location.
Recently, proposals have been made to distribute memory throughout a multiprocessor computer system, rather than use bank(s) of global memory accessible by all processors via a common interconnect bus. More specifically, in distributed memory multiprocessor computer systems, a portion of system memory is physically located adjacent to the processor the memory portion is intended to serve. Research in this area has grown out of attempts to find ways of creating effective multiprocessor computer systems out of a large number of powerful workstations connected together via a network link. In the past, distributed shared memory computer networks have used various software-implemented protocols to share memory space. The software-implemented protocols make the distributed memory simulate a common global memory accessible by all of the computers connected to the network. Memory latency is improved because the portion of memory associated with a specific processor can be accessed by that processor without use of the network link. An example of this research work is the BBN Butterfly computer system developed by BBN Laboratories, Inc. See Butterfly.TM. Parallel Processor Overview, BBN Report No. 6148, Version 1, Mar. 6, 1986, and The Uniform System Approach to Programming the Butterfly.TM. Parallel Processor, BBN Report No. 6149, Version 2, Jun. 16, 1986.
A drawback of the software-implemented protocols used in the BBN Butterfly and the like computer systems is their extremely poor performance when the amount of sharing between processors is large or when the memory associated with a single processor is insufficient to meet the needs of a program and it becomes necessary to use the memory associated with another processor and/or to make data calls to storage devices, such as a hard disk. In the past, such requirements have significantly reduced processing speed. Such requirements have also negatively impacted the bandwidth requirements of the network linking the processors together. A further disadvantage has been the increased overhead associated with the management of data stored at different locations in the distributed memory of the computer system. More specifically, the processing speed of prior art distributed memory multiprocessor computer systems have been improved by replicating shared data in the memories associated with the different processors needing the data. This has a number of disadvantages. First, replicating data in system memory creates a high memory overhead, particularly because system memory is stored on a page basis and page sizes are relatively large. Recently, page sizes of 64K bytes have been proposed. In contrast cache memories store data in blocks of considerably smaller size. A typical cache block of data is 64 bytes. Thus, the "granularity" of the data replicated in system memory is considerably larger than the granularity of data replicated in cache memory. The large granularity size leads to other disadvantages. Greater interconnect bandwidth is required to transfer larger data granules than smaller data granules. Coherency problems are increased because of the likelihood that more processors will be contending for the larger granules than the number contending for smaller granules on a packet-to-packet basis.
In summary, in the last several years, very large-scale integrated circuit (VLSI) processor speeds have been increased by roughly an order of magnitude due to continual semiconductor improvements and due to the introduction of reduced instruction set computer (RISC) architectures. As processor speeds have improved, large, fast and expensive cache memories have been needed in order to reduce average memory latency and keep processor idle times reasonable. Even with improved cache memories and improved ways of maintaining data coherency, average memory latency remains the bottleneck to improving the performance of multiprocessor computer systems.
A major portion of memory latency, i.e., memory access time, is the latency of the network that interconnects the multiprocessors, memory, and input/output modules of multiprocessor computer systems. Regardless of whether the interconnect network is a fully interconnected switching network or a shared bus, the time it takes for a memory request to travel between a processor and system memory is directly added to the actual memory operational latency. Interconnect latency includes not only the actual signal propagation delays, but overhead delays such as synchronization of the interconnect timing environment with the interconnect arbitration, which increases rapidly as processors are added to a multiprocessor system.
Recent attempts to improve memory latency have involved distributing system memory so that it is closer to the processors requiring access to the memory. This has led to sharing data in system memory, which, in turn, has required the implementation of coherency schemes. In the past system memory coherency schemes have been implemented in software. Because they have been implemented in software they have been slow. Further, system memory sharing requires that large data granules be transferred. Large data granules take up large parts of system memory, require large amounts of interconnect bandwidth to transfer from one memory location to another, and are more likely to be referenced by a large number of processors than smaller data granules. The present invention is directed to providing a multiprocessor computer system that overcomes these disadvantages.